package 最小覆盖子串;

import java.util.HashMap;
import java.util.Map;

class Solution {
    //首次尝试
    public String minWindow(String s, String t) {
        String  ret = "";
        int[] hash1 = new int[58];
        char[] str1 = t.toCharArray();
        int m = t.length();
        int kinds = 0;
        for (int i = 0; i < m; i++) {
            hash1[str1[i] - 'A']++;
            if (hash1[str1[i] - 'A'] == 1){
                kinds++;
            }
        }
        int len = s.length();
        char[] str2 = s.toCharArray();
        int[] hash2 = new int[58];
        for (int left = 0,right = 0,count = 0; right < len; right++){
            if (++hash2[str2[right] - 'A'] == hash1[str2[right] - 'A']){
                count++;
            }
            while (count == kinds){
                if (ret.isEmpty() || (ret.length() > (right - left + 1))){
                    ret = s.substring(left, right + 1);
                }
                if (hash2[str2[left] - 'A'] == hash1[str2[left] - 'A']){
                    count--;
                }
                hash2[str2[left] - 'A']--;
                left++;
                while (left < right && count < kinds && hash1[str2[left] - 'A'] == 0){
                    left++;
                }
            }
        }
        return ret;
    }

    //进行优化
    public String minWindow2(String s, String t) {
        char[] str1 = t.toCharArray();
        int[] hash1 = new int[58];
        int kinds = 0;
        for(char c: str1){
            if(hash1[c - 'A']++ == 0){
                kinds++;
            }
        }
        int len = s.length();
        char[] str2 = s.toCharArray();
        int[] hash2 = new int[58];
        int minlen = Integer.MAX_VALUE;
        int begin = -1;
        for(int left = 0,right = 0, count = 0; right < len; right
                ++){
            if(++hash2[str2[right] - 'A'] == hash1[str2[right] - 'A']){
                count++;
            }
            while(count == kinds){
                if(minlen > (right - left + 1)){
                    begin = left;
                    minlen = right - left + 1;
                }
                if(hash2[str2[left] - 'A']-- == hash1[str2[left] - 'A']){
                    count--;
                }
                left++;
            }
        }
        if(begin == -1){
            return new String();
        }
        return s.substring(begin,begin + minlen);
    }
}